27. 移除元素

分析

题目中提到的要原地移除所有数值，说明只能通过覆盖的方式来移动元素，同时返回的内容是 nums 中与 val 不同的元素的数量，这个就很明显了，如果你知道双指针法的话，这里就只用返回慢指针即可。
对于双指针法，我们要明确指针的定义：

快指针指向新元素，用于遍历元素
慢指针为下一个保存筛选过后的元素的索引
因此我们的操作就是：遍历每一个元素，元素与目标值相等的时候，需要同时移动快慢指针，不相等的时候，只需要移动快指针，慢指针不动，这样遍历结束，只看慢指针（从 0 到 慢指针-1 ），就知道所有的筛选过后的元素了。
动图解析：

解题

public int removeElement(int[] nums, int val) {
    int slow=0,fast=0;
    for(;fast<nums.length;fast++){
        // 元素与目标值相等的时候，需要同时移动快慢指针，不相等的时候，只需要移动快指针，慢指针不动
        if(nums[fast]!=val){
            nums[slow]=nums[fast];
            slow++;
        }
    }
    //slow 指的是下一个非val元素插入的位置的索引，而非val元素个数，应该是 slow-1+1 
    // 所以这里直接返回 slow 即可
    return slow;
}

双指针法为什么比两层 for 循环快

双层 for 循环的时候，检测到一次相同元素就会把后续所有元素都往前移动一个位置，不仅存在多余的操作（如果此元素后面也存在目标元素，那目标元素以及后面的元素的的移动就是没有必要的）而且移动效率太低，一次只能移动一格；双指针法没有这些多余操作，只移动一个元素，而且效率很高（直接从之前的位置，到最终的位置，移动之后不会再移动），所以双指针法快
双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组、链表、字符串等操作的面试题，都使用双指针法。
只要是要求在原数组上移除元素的，几乎都是用双指针

27. 移除元素

分析

解题

双指针法为什么比两层 for 循环快

相关题